package main

import "fmt"

// BubbleSort 冒泡排序
func BubbleSort(arr *[]int) {
	fmt.Println("排序前：", *arr)
	temp := 0 //临时变量
	// 循环体
	for i := 0; i < len(*arr)-1; i++ {
		for j := 0; j < len(*arr)-1-i; j++ { //-i是为了节省内存
			if (*arr)[j] > (*arr)[j+1] {
				// 交换
				temp = (*arr)[j]        //第一个赋值给临时变量（最大）
				(*arr)[j] = (*arr)[j+1] // 小的给大的
				(*arr)[j+1] = temp      // 最大的给最小的
			}
		}
	}
	fmt.Println("排序后：", *arr)
}

// QuickSort 快速排序
func QuickSort(arr *[]int, leftIndex int, rightIndex int) {
	/*if leftIndex >= rightIndex {
		return
	}
	left, right := leftIndex, rightIndex
	key := (*arr)[(leftIndex+rightIndex)/2] //选取中心轴
	for left < right {
		for left < right && (*arr)[right] >= key {
			right--
		}
		if left < right {
			(*arr)[left] = (*arr)[right]
		}
		for left < right && (*arr)[left] <= key {
			left++
		}
		if left < right {
			(*arr)[right] = (*arr)[left]
		}
		if left >= right {
			(*arr)[left] = key
		}
	}
	QuickSort(arr, leftIndex, right-1)
	QuickSort(arr, right+1, right)*/
	if leftIndex < rightIndex {
		left, right := leftIndex, rightIndex
		key := (*arr)[(leftIndex+rightIndex)/2] //选取中心轴
		fmt.Println("开始进入的arr：", arr)
		fmt.Println("中心轴：", key)
		for left <= right {
			for (*arr)[left] < key { // 当arr[i]<key基准值，从左往右不断扫描
				left++
			}
			for (*arr)[right] > key { // 当arr[i]>key基准值，从右往左不断扫描
				right--
			}
			if left <= right { //交换 arr[i]和 a[j]的元素
				(*arr)[left], (*arr)[right] = (*arr)[right], (*arr)[left]
				left++
				right--
				fmt.Println("交换后的arr：", arr)
			}
		}
		if leftIndex < right { // 当right -- 到等于leftIndex(0)的时候，递归终止
			QuickSort(arr, leftIndex, right)
		}
		if rightIndex > left {
			QuickSort(arr, left, rightIndex)
		}
		fmt.Println("交换后arr：", arr)
	}
}

func main() {
	slices := []int{5, 15, 98, 8, 4, 7}
	BubbleSort(&slices)

	arr := []int{3, 7, 9, 8, 38, 93, 12, 222, 45, 93, 23, 84, 65, 2}
	QuickSort(&arr, 0, len(arr)-1)
	fmt.Println(arr)
}
